// 给定一个数组nums，数组中值互不相同，数组中的值经过了升序排列又进行了旋转，再给定一个target,要求从nums中找到target所在位置，
// 如果找到，则返回对应下标，找不到则返回-1

// 思路：二分查找，利用有序数组旋转后的有序序列进行查找
// 判断左侧还是右侧有序，在有序序列中进行判断并更新left和right指针

function search(arr, target) {
    let left = 0
    let right = arr.length - 1
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left
        if (arr[mid] === target) {
            return mid
        }
        // 左侧有序
        if (arr[mid] >= arr[left]) {
            // 大于等于不能漏掉left
            if (target >= arr[left] && target < arr[mid]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // 这里的小于等于，不能漏掉right
            if (target > arr[mid] && target <= arr[right]) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

let nums = [4, 5, 6, 7, 0, 1, 2]
let target = 0

console.log(search(nums, target))